⟸ Go Back ⟸

Exercise 11 (Homework 4).

(context-free languages, depuration of grammars, regular languages, linear grammar, regular grammar, ambiguity)

On regular grammars

A context-free grammar G=(V,\Sigma,P,S) is right linear if all its productions are of the form A \to wB or A \to w, where A, B \in V and w \in \Sigma^*. Analogously, when all the productions of G are of the form A \to Bw or A \to w, we say that G is left linear. A grammar which is either right linear or left linear is called regular. If the grammar G contains productions of the form A \to wB, A \to Bw, or A \to w, we say that G is linear.

The goal of this exercise is to show that regular languages can be generated by unambiguous grammars.

1. Normal form. Prove that for every right-linear grammar G=(V,\Sigma,P,S) there exists an equivalent grammar whose productions are all of the form A \to aB or A \to \lambda, where A, B \in V and a \in \Sigma. Observe that a symmetric transformation can be applied to left-linear grammars.

2. Linear grammars. Construct a linear grammar generating a non-regular language.

3. Regular grammars. Prove that a language is regular if and only if it is generated by a regular grammar.

   Tip

   Show this only for left-linear o right-linear grammars (it can be done independently for any of them and they are symmetric). Use the normal form above.

4. Unambiguity of regular languages. Show that the regular languages can be generated by unambiguous grammars.

   Tip

   Use the construction from the previous item to transform a DFA into a regular grammar and show that the obtained grammar is unambiguous.